// 二叉搜索树中第K小的元素

package Leetcode;

import java.util.Deque;
import java.util.LinkedList;

class Solution_230 {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new LinkedList<>();
        int count = 0;
        while (root != null || !stack.isEmpty()) {
            // 向左走到尽头
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            // 栈顶元素出栈，并访问
            root = stack.pop();
            if (++count == k)
                return root.val;
            // 获得栈顶元素的右子树，如果为null，则在下一次循环中栈顶元素会接着出栈直至找到有右子树的栈顶
            root = root.right;
        }
        return 0;
    }

/*     public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new LinkedList<>();
        int count = 0;
        while (root != null || !stack.isEmpty()) {
            // 向左走到尽头
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            // 栈顶元素出栈，并访问
            root = stack.pop();
            if (++count == k)
                return root.val;
            // 获得栈顶元素的右子树，如果为null，则在下一次循环中栈顶元素会接着出栈直至找到有右子树的栈顶
            root = root.right;
        }
        return 0;
    } */
}